#include "../tools.h"

/**
 * pre, pl, pr, in, il, ir
 * 
 * pre, pl + 1, pl + len_l, in, il, index - 1
 * pre, pl + len_l + 1, pr, in, index + 1, ir
 */
class Solution {
public:
    TreeNode* helper(vector<int>& pre, int pl, int pr, vector<int>& vin, int il, int ir){
        if(pl > pr) return nullptr;

        int rval = pre[pl];
        int index = il;
        while(index < ir){
            if(vin[index] == rval) break;
            ++index;
        }
        int len_l = index - il;
        
        TreeNode* root = new TreeNode(rval);
        root->left = helper(pre, pl + 1, pl + len_l, vin, il, index - 1);
        root->right = helper(pre, pl + len_l + 1, pr, vin, index + 1, ir);
        return root;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if (pre.size() == 0) return nullptr;
        return helper(pre, 0, pre.size() - 1, vin, 0, vin.size() - 1);
    }
};


int main(int argc, char const *argv[])
{
    
    // int arr[] = {1, 2, 3, 4, -1, 5, 6, -1, 7, -1, -1, 8};
    // int size = sizeof(arr) / sizeof(int);

    // TreeNode* tree = create_tree(arr, size);
    // show(tree);

    vector<int> pre = {1,2,4,7,3,5,6,8};
    vector<int> in  = {4,7,2,1,5,3,8,6};

    Solution s;
    TreeNode* tree = s.reConstructBinaryTree(pre, in);
    show(tree);



    return 0;
}
